﻿Imports System
Imports System.Text
Imports System.Collections.Generic
Imports Microsoft.VisualStudio.TestTools.UnitTesting

<TestClass()> Public Class AlgoritmosBusca

    Private testContextInstance As TestContext

    '''<summary>
    '''Gets or sets the test context which provides
    '''information about and functionality for the current test run.
    '''</summary>
    Public Property TestContext() As TestContext
        Get
            Return testContextInstance
        End Get
        Set(ByVal value As TestContext)
            testContextInstance = Value
        End Set
    End Property

#Region "Additional test attributes"
    '
    ' You can use the following additional attributes as you write your tests:
    '
    ' Use ClassInitialize to run code before running the first test in the class
    ' <ClassInitialize()> Public Shared Sub MyClassInitialize(ByVal testContext As TestContext)
    ' End Sub
    '
    ' Use ClassCleanup to run code after all tests in a class have run
    ' <ClassCleanup()> Public Shared Sub MyClassCleanup()
    ' End Sub
    '
    ' Use TestInitialize to run code before running each test
    ' <TestInitialize()> Public Sub MyTestInitialize()
    ' End Sub
    '
    ' Use TestCleanup to run code after each test has run
    ' <TestCleanup()> Public Sub MyTestCleanup()
    ' End Sub
    '
#End Region

    <TestMethod()> Public Sub Busca_Sequencial()

        Dim _arrayValores() As Integer
        Dim _valores As List(Of Integer) = New List(Of Integer)
        Dim generator As New Random
        Dim randomValue As Integer
        randomValue = generator.Next(0, 500)

        For i As Integer = 1 To 500
            _valores.Add(i)
        Next

        _arrayValores = _valores.ToArray

        '-- comecando a busca
        For i = 0 To (_arrayValores.Length - 1)
            Console.Write("|")
            If _arrayValores(i).Equals(randomValue) Then Console.Write(i) : Exit For
        Next

        Assert.IsTrue(True)

    End Sub

    <TestMethod()> Public Sub Busca_Sequencial01()

        Dim generator As New Random
        Dim randomValue As Integer
        randomValue = generator.Next(0, 500)

        For i = 1 To 10
            BuscaSequencial_Elementos_Ordenados(randomValue, 500)
            Threading.Thread.Sleep(300)
            randomValue = generator.Next(0, 500)
        Next

        Assert.IsTrue(True)

    End Sub

    <TestMethod()> Public Sub Busca_Binaria01()

        Dim generator As New Random
        Dim randomValue As Integer
        randomValue = generator.Next(0, 500)

        For i = 1 To 10
            BuscaBinaria_Elementos_Ordenados(randomValue, 500)
            Threading.Thread.Sleep(300)
            randomValue = generator.Next(0, 500)
        Next

        Assert.IsTrue(True)

    End Sub

    '    Para iniciarmos nossas discussões gostaria que explicassem as estratégias de busca binária e de busca sequencial. 
    'E em seguida discutisse a eficicência destes algoritmos para alguns casos a saber:

    'a) Quando o conjunto de dados estiver ordenado e o dado procurado não se encontrar no conjunto
    'b) Quando o conjunto de dados estiver desordenado
    'c) Quando o conjunto de dados estiver ordenado, mas o dado procurado apresentar alta probabilidade de se encontrar nas primeiras posições do vetor.
    '
    <TestMethod()> Public Sub Comparando_Binaria_Sequencial_Em_Caso_Ordenado01()

        Dim generator As New Random
        Dim randomValue As Integer
        randomValue = generator.Next(0, 500)

        For i = 1 To 10
            BuscaBinaria_Elementos_Ordenados(randomValue, 500)
            BuscaSequencial_Elementos_Ordenados(randomValue, 500)
            Threading.Thread.Sleep(300)
            randomValue = generator.Next(0, 500)
        Next

        Assert.IsTrue(True)
    End Sub


    <TestMethod()> Public Sub Busca_Sequencial_Desordenada01()

        Dim _nrElementos As Integer = 500
        Dim _arrayValores() As Integer
        Dim _valores As List(Of Integer) = New List(Of Integer)
        Dim generator As New Random
        Dim _elementoBuscado As Integer

        For i As Integer = 0 To _nrElementos
            Dim randomValue As Integer
            randomValue = generator.Next(0, (_nrElementos * 2))
            _valores.Add(randomValue)
            Threading.Thread.Sleep(55)
        Next

        _elementoBuscado = generator.Next(0, (_nrElementos * 2))
        _arrayValores = _valores.ToArray

        For Each _valor In _arrayValores
            Console.Write("{0}|", _valor)
        Next
        Console.WriteLine()
        Console.WriteLine("Elemento sorteado: {0}", _elementoBuscado)

        BuscaSequencial_Elementos(_elementoBuscado, _arrayValores)

        Assert.IsTrue(True)

    End Sub


    <TestMethod()> Public Sub Busca_Sequencial_Desordenada02()

        Dim _nrElementos As Integer = 500
        Dim _arrayValores() As Integer
        Dim _valores As List(Of Integer) = New List(Of Integer)
        Dim generator As New Random
        Dim _elementoBuscado As Integer

        For i As Integer = 0 To _nrElementos
            _valores.Add(i)
            Threading.Thread.Sleep(55)
        Next

        _valores = DesordenandoArray(_valores.ToArray)

        _elementoBuscado = generator.Next(0, _nrElementos)
        _arrayValores = _valores.ToArray

        For Each _valor In _arrayValores
            Console.Write("{0}|", _valor)
        Next
        Console.WriteLine()
        Console.WriteLine("Elemento sorteado: {0}", _elementoBuscado)

        BuscaSequencial_Elementos(_elementoBuscado, _arrayValores)

        Assert.IsTrue(True)

    End Sub

    <TestMethod()> Public Sub Busca_Binaria_DESORdenada()

        Dim generator As New Random
        Dim randomValue As Integer

        For i = 1 To 10
            'BuscaBinaria_Elementos_Ordenados(randomValue, 500)
            'BuscaSequencial_Elementos_Ordenados(randomValue, 500)
            randomValue = generator.Next(0, 500)
            Console.WriteLine("Elemento sorteado: {0}", randomValue)
            Me.BuscaBinaria_Elementos_DESOrdenados(randomValue, 500)
            Me.BuscaSequencial_Elementos_DESOrdenados(randomValue, 500)
            Threading.Thread.Sleep(300)
            randomValue = generator.Next(0, 500)
        Next

        Assert.IsTrue(True)

    End Sub

    Protected Sub BuscaSequencial_Elementos_Ordenados(ByVal _elementoBuscado As Integer, ByVal _nrElementos As Integer)

        Dim _arrayValores() As Integer
        Dim _valores As List(Of Integer) = New List(Of Integer)

        For i As Integer = 0 To _nrElementos
            _valores.Add(i)
        Next

        _arrayValores = _valores.ToArray

        '-- comecando a busca
        For i = 0 To (_arrayValores.Length - 1)
            Console.Write("|")
            If _arrayValores(i).Equals(_elementoBuscado) Then Console.Write("custo {0}={1} ", i, _arrayValores(i)) : Console.WriteLine() : Exit For
        Next

    End Sub

    Protected Sub BuscaBinaria_Elementos_DESOrdenados(ByVal _elementoBuscado As Integer, ByVal _nrElementos As Integer)

        Dim _arrayValores() As Integer
        Dim _valores As List(Of Integer) = New List(Of Integer)
        Dim generator As New Random
        Dim _valorMeio As Integer
        Dim _indiceInferior As Integer = 0
        Dim _indiceSuperior As Integer
        Dim _interacoes As Integer = 0

        For i As Integer = 0 To _nrElementos
            _valores.Add(i)
        Next

        _valores = DesordenandoArray(_valores.ToArray)
        _arrayValores = _valores.ToArray

        _indiceSuperior = _arrayValores.Length - 1

        '-- comecando a busca
        While _indiceInferior <= _indiceSuperior
            _interacoes += 1
            _valorMeio = _indiceInferior + ((_indiceSuperior - _indiceInferior) / 2)
            Console.Write(":")
            If _valores(_valorMeio) < _elementoBuscado Then
                _indiceInferior = _valorMeio + 1
            ElseIf _valores(_valorMeio) > _elementoBuscado Then
                _indiceSuperior = _valorMeio - 1
            Else
                'Return _valorMeio
                Console.Write("custo {0}={1}", _interacoes, _valorMeio) : Console.WriteLine()
                Exit Sub
            End If
        End While

        Console.Write("NOT_FOUND") : Console.WriteLine()

    End Sub

    Protected Sub BuscaSequencial_Elementos_DESOrdenados(ByVal _elementoBuscado As Integer, ByVal _nrElementos As Integer)

        Dim _arrayValores() As Integer
        Dim _valores As List(Of Integer) = New List(Of Integer)

        For i As Integer = 0 To _nrElementos
            _valores.Add(i)
        Next

        _valores = Me.DesordenandoArray(_valores.ToArray)
        _arrayValores = _valores.ToArray

        '-- comecando a busca
        For i = 0 To (_arrayValores.Length - 1)
            Console.Write("|")
            If _arrayValores(i).Equals(_elementoBuscado) Then Console.Write("custo {0}={1} ", i, _arrayValores(i)) : Console.WriteLine() : Exit For
        Next

    End Sub



    <TestMethod()> Public Sub Ordena_BubleSort()

        Dim _arrayValores() As Integer
        Dim _valores As List(Of Integer) = New List(Of Integer)

        For i As Integer = 0 To 100
            _valores.Add(i)
        Next

        _valores = Me.DesordenandoArray(_valores.ToArray)
        _arrayValores = _valores.ToArray

        Me.BubbleSort(_arrayValores, 0, (_arrayValores.Count - 1))

        Assert.IsTrue(True)

    End Sub


    'Sub Selectionsort(ByVal List() As Long, ByVal min As Integer, ByVal max As Integer)
    <TestMethod()> Public Sub Ordena_Selectionsort()

        Dim _arrayValores() As Integer
        Dim _valores As List(Of Integer) = New List(Of Integer)

        For i As Integer = 0 To 100
            _valores.Add(i)
        Next

        _valores = Me.DesordenandoArray(_valores.ToArray)
        _arrayValores = _valores.ToArray

        Me.Selectionsort(_arrayValores, 0, (_arrayValores.Count - 1))

        Assert.IsTrue(True)

    End Sub


    'http://www.vb-helper.com/tut1.htm#Quicksort
    'Sub Quicksort(ByVal _arrayValores() As Integer, ByVal min As Integer, ByVal max As Integer)
    <TestMethod()> Public Sub Ordena_Quicksort()

        Dim _arrayValores() As Integer
        Dim _valores As List(Of Integer) = New List(Of Integer)

        For i As Integer = 0 To 100
            _valores.Add(i)
        Next

        _valores = Me.DesordenandoArray(_valores.ToArray)
        _arrayValores = _valores.ToArray

        Me.Quicksort(_arrayValores, 0, (_arrayValores.Count - 1))

        Assert.IsTrue(True)

    End Sub


    'http://www.vb-helper.com/tut1.htm#Bubblesort
    ' min and max are the minimum and maximum indexes
    ' of the items that might still be out of order.
    Sub BubbleSort(ByVal _array() As Integer, ByVal min As Integer, ByVal max As Integer)
        Dim last_swap As Integer
        Dim i As Integer
        Dim j As Integer
        Dim tmp As Long

        ' Repeat until we are done.
        Do While min < max
            Console.Write("a")
            ' Bubble up.
            last_swap = min - 1
            ' For i = min + 1 To max
            i = min + 1
            Do While i <= max
                Console.Write("b")
                ' Find a bubble.
                If _array(i - 1) > _array(i) Then
                    ' See where to drop the bubble.
                    tmp = _array(i - 1)
                    j = i
                    Do
                        _array(j - 1) = _array(j)
                        j = j + 1
                        If j > max Then Exit Do
                    Loop While _array(j) < tmp
                    _array(j - 1) = tmp
                    last_swap = j - 1
                    i = j + 1
                Else
                    i = i + 1
                End If
            Loop
            ' Update max.
            max = last_swap - 1

            ' Bubble down.
            last_swap = max + 1
            ' For i = max - 1 To min Step -1
            i = max - 1
            Console.WriteLine()
            Do While i >= min
                Console.Write("c")
                ' Find a bubble.
                If _array(i + 1) < _array(i) Then
                    ' See where to drop the bubble.
                    tmp = _array(i + 1)
                    j = i
                    Do
                        _array(j + 1) = _array(j)
                        j = j - 1
                        If j < min Then Exit Do
                    Loop While _array(j) > tmp
                    _array(j + 1) = tmp
                    last_swap = j + 1
                    i = j - 1
                Else
                    i = i - 1
                End If
            Loop
            ' Update min.
            min = last_swap + 1
        Loop
    End Sub

    'http://www.vb-helper.com/tut1.htm#Selectionsort
    Sub Selectionsort(ByVal _arrayValores() As Integer, ByVal min As Integer, ByVal max As Integer)
        Dim i As Integer
        Dim j As Integer
        Dim best_value As Long
        Dim best_j As Integer

        For i = min To max - 1
            Console.Write("a")
            best_value = _arrayValores(i)
            best_j = i
            For j = i + 1 To max
                Console.Write("b")
                If _arrayValores(j) < best_value Then
                    Console.Write("c")
                    best_value = _arrayValores(j)
                    best_j = j
                End If
            Next j
            _arrayValores(best_j) = _arrayValores(i)
            _arrayValores(i) = best_value
            Console.WriteLine()
        Next i
    End Sub

    Sub Quicksort(ByVal _arrayValores() As Integer, ByVal min As Integer, ByVal max As Integer)
        Dim med_value As Long
        Dim hi As Integer
        Dim lo As Integer
        Dim i As Integer

        ' If the list has no more than 1 element, it's sorted.
        If min >= max Then Exit Sub

        ' Pick a dividing item.
        i = Int((max - min + 1) * Rnd() + min)
        med_value = _arrayValores(i)

        ' Swap it to the front so we can find it easily.
        _arrayValores(i) = _arrayValores(min)

        ' Move the items smaller than this into the left
        ' half of the list. Move the others into the right.
        lo = min
        hi = max
        Do
            Console.Write("a")
            ' Look down from hi for a value < med_value.
            Do While _arrayValores(hi) >= med_value
                Console.Write("b")
                hi = hi - 1
                If hi <= lo Then Exit Do
            Loop
            If hi <= lo Then
                _arrayValores(lo) = med_value
                Exit Do
            End If

            ' Swap the lo and hi values.
            _arrayValores(lo) = _arrayValores(hi)

            ' Look up from lo for a value >= med_value.
            lo = lo + 1
            Do While _arrayValores(lo) < med_value
                Console.Write("c")
                lo = lo + 1
                If lo >= hi Then Exit Do
            Loop
            If lo >= hi Then
                lo = hi
                _arrayValores(hi) = med_value
                Exit Do
            End If

            ' Swap the lo and hi values.
            _arrayValores(hi) = _arrayValores(lo)
            Console.WriteLine()
        Loop

        ' Sort the two sublists
        Quicksort(_arrayValores, min, lo - 1)
        Quicksort(_arrayValores, lo + 1, max)
    End Sub



    Protected Sub BuscaBinaria_Elementos_Ordenados(ByVal _elementoBuscado As Integer, ByVal _nrElementos As Integer)

        Dim _arrayValores() As Integer
        Dim _valores As List(Of Integer) = New List(Of Integer)
        Dim generator As New Random
        Dim _valorMeio As Integer
        Dim _indiceInferior As Integer = 0
        Dim _indiceSuperior As Integer
        Dim _interacoes As Integer = 0

        For i As Integer = 0 To _nrElementos
            _valores.Add(i)
        Next

        _arrayValores = _valores.ToArray

        _indiceSuperior = _arrayValores.Length - 1

        '-- comecando a busca
        While _indiceInferior <= _indiceSuperior
            _interacoes += 1
            _valorMeio = _indiceInferior + ((_indiceSuperior - _indiceInferior) / 2)
            Console.Write(":")
            If _valores(_valorMeio) < _elementoBuscado Then
                _indiceInferior = _valorMeio + 1
            ElseIf _valores(_valorMeio) > _elementoBuscado Then
                _indiceSuperior = _valorMeio - 1
            Else
                'Return _valorMeio
                Console.Write("custo {0}={1}", _interacoes, _valorMeio) : Console.WriteLine()
                Exit Sub
            End If
        End While

        Console.Write("NOT_FOUND") : Console.WriteLine()

    End Sub

    Protected Sub BuscaSequencial_Elementos(ByVal _elementoBuscado As Integer, ByVal _arrayValores() As Integer)

        Dim _valores As List(Of Integer) = New List(Of Integer)

        '-- comecando a busca
        For i = 0 To (_arrayValores.Length - 1)
            Console.Write("|")
            If _arrayValores(i).Equals(_elementoBuscado) Then Console.Write("custo {0}={1} ", i, _arrayValores(i)) : Console.WriteLine() : Exit Sub
        Next
        Console.Write("custo {0}={1} ", (_arrayValores.Length - 1), "NAO_ENCONTRADO")

    End Sub

    Protected Sub BuscaBinaria_Elementos(ByVal _elementoBuscado As Integer, ByVal _arrayValores() As Integer)

        Dim generator As New Random
        Dim _valorMeio As Integer
        Dim _indiceInferior As Integer = 0
        Dim _indiceSuperior As Integer
        Dim _interacoes As Integer = 0

        _indiceSuperior = _arrayValores.Length - 1

        '-- comecando a busca
        While _indiceInferior <= _indiceSuperior
            _interacoes += 1
            _valorMeio = _indiceInferior + ((_indiceSuperior - _indiceInferior) / 2)
            Console.Write(":")
            If _arrayValores(_valorMeio) < _elementoBuscado Then
                _indiceInferior = _valorMeio + 1
            ElseIf _arrayValores(_valorMeio) > _elementoBuscado Then
                _indiceSuperior = _valorMeio - 1
            Else
                'Return _valorMeio
                Console.Write("custo {0}={1}", _interacoes, _valorMeio) : Console.WriteLine()
                Exit Sub
            End If
        End While

        Console.Write("NOT_FOUND") : Console.WriteLine()

    End Sub

    Protected Function DesordenandoArray(ByVal items() As Integer) As IList(Of Integer)

        Dim max_index As Integer = items.Length - 1
        Dim rnd As New Random
        For i As Integer = 0 To max_index - 1
            ' Pick an item for position i.
            Dim j As Integer = rnd.Next(i, max_index + 1)

            ' Swap them.
            Dim temp As Integer = items(i)
            items(i) = items(j)
            items(j) = temp
        Next i

        Return items.ToList()

    End Function


End Class
